{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct String With Repeat Limit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #counting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #计数 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: repeatLimitedString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造限制重复的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个整数 <code>repeatLimit</code> ，用 <code>s</code> 中的字符构造一个新字符串 <code>repeatLimitedString</code> ，使任何字母 <strong>连续</strong> 出现的次数都不超过 <code>repeatLimit</code> 次。你不必使用 <code>s</code> 中的全部字符。</p>\n",
    "\n",
    "<p>返回 <strong>字典序最大的</strong><em> </em><code>repeatLimitedString</code> 。</p>\n",
    "\n",
    "<p>如果在字符串 <code>a</code> 和 <code>b</code> 不同的第一个位置，字符串 <code>a</code> 中的字母在字母表中出现时间比字符串 <code>b</code> 对应的字母晚，则认为字符串 <code>a</code> 比字符串 <code>b</code> <strong>字典序更大</strong> 。如果字符串中前 <code>min(a.length, b.length)</code> 个字符都相同，那么较长的字符串字典序更大。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"cczazcc\", repeatLimit = 3\n",
    "<strong>输出：</strong>\"zzcccac\"\n",
    "<strong>解释：</strong>使用 s 中的所有字符来构造 repeatLimitedString \"zzcccac\"。\n",
    "字母 'a' 连续出现至多 1 次。\n",
    "字母 'c' 连续出现至多 3 次。\n",
    "字母 'z' 连续出现至多 2 次。\n",
    "因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。\n",
    "该字符串是字典序最大的 repeatLimitedString ，所以返回 \"zzcccac\" 。\n",
    "注意，尽管 \"zzcccca\" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"aababab\", repeatLimit = 2\n",
    "<strong>输出：</strong>\"bbabaa\"\n",
    "<strong>解释：</strong>\n",
    "使用 s 中的一些字符来构造 repeatLimitedString \"bbabaa\"。 \n",
    "字母 'a' 连续出现至多 2 次。 \n",
    "字母 'b' 连续出现至多 2 次。 \n",
    "因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。 \n",
    "该字符串是字典序最大的 repeatLimitedString ，所以返回 \"bbabaa\" 。 \n",
    "注意，尽管 \"bbabaaa\" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= repeatLimit &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-string-with-repeat-limit](https://leetcode.cn/problems/construct-string-with-repeat-limit/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-string-with-repeat-limit](https://leetcode.cn/problems/construct-string-with-repeat-limit/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cczazcc\"\\n3', '\"aababab\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "       n = len(s)\n",
    "       res = \"\"\n",
    "       cnts = [0] * 26\n",
    "       for c in s:\n",
    "          cnts[ord(c) - ord('a')] += 1\n",
    "       for i in range(25, -1, -1):\n",
    "          while cnts[i] > 0:\n",
    "             if cnts[i] <= repeatLimit:\n",
    "                while cnts[i] > 0:\n",
    "                   res += chr(ord('a') + i)\n",
    "                   cnts[i] -= 1\n",
    "             else:\n",
    "                for j in range(repeatLimit):\n",
    "                   res += chr(ord('a') + i)\n",
    "                j = i - 1\n",
    "                while j >= 0:\n",
    "                   if cnts[j]:\n",
    "                      res += chr(ord('a') + j)\n",
    "                      cnts[j] -= 1\n",
    "                      break\n",
    "                   j -= 1\n",
    "                if j < 0:\n",
    "                   return res\n",
    "                cnts[i] -= repeatLimit\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        kv = [[k, v] for k, v in Counter(s).items()]\n",
    "        kv.sort(reverse=True)\n",
    "        n = len(kv)\n",
    "        ret = ''\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        while i < n:\n",
    "            if kv[i][1] <= repeatLimit:\n",
    "                ret += kv[i][0] * kv[i][1]\n",
    "                i, j = j, j + 1\n",
    "            else:\n",
    "                ret += kv[i][0] * repeatLimit\n",
    "                kv[i][1] -= repeatLimit\n",
    "                if j >= n:\n",
    "                    break\n",
    "                ret += kv[j][0]\n",
    "                kv[j][1] -= 1\n",
    "                if kv[j][1] == 0:\n",
    "                    j += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt=Counter(s)\n",
    "        res=sorted(cnt.keys())\n",
    "        ans=\"\"\n",
    "        while res:\n",
    "            temp=res.pop()\n",
    "            if cnt[temp]<=repeatLimit:\n",
    "                ans+=temp*cnt[temp]\n",
    "                if not res:\n",
    "                    break\n",
    "            else:\n",
    "                ans+=temp*repeatLimit\n",
    "                cnt[temp]-=repeatLimit\n",
    "                if res:\n",
    "                    m=res[-1]\n",
    "                    ans+=m\n",
    "                    cnt[m]-=1\n",
    "                    if cnt[m]==0:\n",
    "                        res.pop()\n",
    "                    res.append(temp)\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, k: int) -> str:\n",
    "        C = Counter(s)\n",
    "        q = []\n",
    "        for idx,c in C.items():\n",
    "            heappush(q,(-ord(idx),c))\n",
    "        # print(q)\n",
    "        res = '_'\n",
    "        while len(q) > 1:\n",
    "            i1,v1 = heappop(q)\n",
    "            c1 = chr(-i1)\n",
    "            if res[-1] != c1:\n",
    "                if k >= v1:\n",
    "                    res += v1 * c1\n",
    "                else:\n",
    "                    res += k * c1;heappush(q,(i1,v1-k))\n",
    "            else:\n",
    "                i2,v2 = heappop(q)\n",
    "                c2 = chr(-i2)\n",
    "                res += c2\n",
    "                if v2 != 1:\n",
    "                    heappush(q,(i2,v2-1))\n",
    "                heappush(q,(i1,v1))\n",
    "        i1,v1 = heappop(q)\n",
    "        c1 = chr(-i1)\n",
    "        if res[-1] != c1:\n",
    "            res += min(v1,k) * c1\n",
    "        return res[1:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        arr = sorted([[c, cnt] for c, cnt in Counter(s).items()], reverse=True)\n",
    "        ans = ''\n",
    "        cnt = defaultdict(int)\n",
    "        while arr:\n",
    "            # print(ans, arr, cnt)\n",
    "            if cnt[arr[0][0]] < repeatLimit:\n",
    "                if ans and ans[-1] != arr[0][0]:\n",
    "                    cnt = defaultdict(int)\n",
    "                ans += arr[0][0]\n",
    "                arr[0][1] -= 1\n",
    "                cnt[arr[0][0]] += 1\n",
    "                if arr[0][1] == 0:\n",
    "                    arr.pop(0)\n",
    "            else:\n",
    "                if len(arr) == 1:\n",
    "                    break\n",
    "                cnt[arr[0][0]] = 0\n",
    "                ans += arr[1][0]\n",
    "                arr[1][1] -= 1\n",
    "                cnt[arr[1][0]] += 1\n",
    "                cnt[arr[0][0]] = 0\n",
    "                if arr[1][1] == 0:\n",
    "                    arr.pop(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        hashmap = Counter(s)\n",
    "        maxHeap = [[-ord(char), hashmap[char], char] for char in hashmap]\n",
    "        heapq.heapify(maxHeap)\n",
    "        ans = ''\n",
    "\n",
    "        while maxHeap:\n",
    "            ordx, countx, x = heapq.heappop(maxHeap)\n",
    "\n",
    "            if len(ans) >= repeatLimit and ans[-repeatLimit:] == x*repeatLimit:\n",
    "                if not maxHeap:\n",
    "                    return ans \n",
    "                else:\n",
    "                    ordy, county, y = heapq.heappop(maxHeap) \n",
    "                    ans += y\n",
    "                    heapq.heappush(maxHeap, [ordx, countx, x])\n",
    "                    if county-1: heapq.heappush(maxHeap, [ordy, county-1, y])\n",
    "            else:\n",
    "                ans += x\n",
    "                if countx-1: heapq.heappush(maxHeap, [ordx, countx-1, x])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        q = []\n",
    "        for k, v in cnt.items():\n",
    "            heapq.heappush(q, (-ord(k), v))\n",
    "\n",
    "        ans = ''\n",
    "        pre = ''\n",
    "        while q:\n",
    "            k, v = heapq.heappop(q)\n",
    "            ch = chr(-k)\n",
    "            rl = repeatLimit - (ch == pre)\n",
    "            if v >= rl:\n",
    "                ans += ch * rl\n",
    "                v -= rl\n",
    "                if not q:\n",
    "                    break\n",
    "                else:\n",
    "                    k1, v1 = heapq.heappop(q)\n",
    "                    ch1 = chr(-k1)\n",
    "                    ans += ch1\n",
    "                    v1 -= 1\n",
    "                    pre = ch1\n",
    "                    if v1:\n",
    "                        heapq.heappush(q, (k1, v1))\n",
    "                if v:\n",
    "                    heapq.heappush(q, (k, v))\n",
    "            else:\n",
    "                ans += ch * v\n",
    "                pre = ch\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        mapping = {}\n",
    "        for c in s:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        heap = []\n",
    "        for c in mapping:\n",
    "            heapq.heappush(heap,[-ord(c),c,mapping[c]])\n",
    "        pre = ''\n",
    "        result = ''\n",
    "        while(heap):\n",
    "            ordc, c, cnt = heapq.heappop(heap)\n",
    "            if(c != pre):\n",
    "                result += c*min(cnt,repeatLimit)\n",
    "                cnt -= min(cnt,repeatLimit)\n",
    "                pre = c \n",
    "                if(cnt > 0):\n",
    "                    heapq.heappush(heap,[ordc, c, cnt])\n",
    "            else:\n",
    "                if(len(heap) == 0):\n",
    "                    break\n",
    "                ordc1, c1, cnt1 = heapq.heappop(heap)\n",
    "                result += c1\n",
    "                cnt1 -= 1\n",
    "                pre = c1 \n",
    "                if(cnt1 > 0):\n",
    "                    heapq.heappush(heap,[ordc1, c1, cnt1])\n",
    "                heapq.heappush(heap,[ordc, c, cnt])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        mapping = {}\n",
    "        for c in s:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        heap = []\n",
    "        for c in mapping:\n",
    "            heapq.heappush(heap,[-ord(c),c,mapping[c]])\n",
    "        pre = ''\n",
    "        result = ''\n",
    "        while(heap):\n",
    "            ordc, c, cnt = heapq.heappop(heap)\n",
    "            if(c != pre):\n",
    "                result += c*min(cnt,repeatLimit)\n",
    "                cnt -= min(cnt,repeatLimit)\n",
    "                pre = c \n",
    "                if(cnt > 0):\n",
    "                    heapq.heappush(heap,[ordc, c, cnt])\n",
    "            else:\n",
    "                if(len(heap) == 0):\n",
    "                    break\n",
    "                ordc1, c1, cnt1 = heapq.heappop(heap)\n",
    "                result += c1\n",
    "                cnt1 -= 1\n",
    "                pre = c1 \n",
    "                if(cnt1 > 0):\n",
    "                    heapq.heappush(heap,[ordc1, c1, cnt1])\n",
    "                heapq.heappush(heap,[ordc, c, cnt])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        kv = [[k, v] for k, v in Counter(s).items()]\n",
    "        kv.sort(reverse=True)\n",
    "        n = len(kv)\n",
    "        ret = ''\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        while i < n:\n",
    "            if kv[i][1] <= repeatLimit:\n",
    "                ret += kv[i][0] * kv[i][1]\n",
    "                i, j = j, j + 1\n",
    "            else:\n",
    "                ret += kv[i][0] * repeatLimit\n",
    "                kv[i][1] -= repeatLimit\n",
    "                if j >= n:\n",
    "                    break\n",
    "                ret += kv[j][0]\n",
    "                kv[j][1] -= 1\n",
    "                if kv[j][1] == 0:\n",
    "                    j += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        i, r = 25, repeatLimit\n",
    "        ans = \"\"\n",
    "        while i >= 0:\n",
    "            c = chr(ord('a') + i)\n",
    "            while cnt[c]:\n",
    "                v = min(r, cnt[c])\n",
    "                ans += c * v\n",
    "                cnt[c] -= v\n",
    "                if cnt[c]:\n",
    "                    ok = False\n",
    "                    for j in range(i-1, -1, -1):\n",
    "                        c2 = chr(ord('a') + j)\n",
    "                        if cnt[c2]:\n",
    "                            ans += c2 \n",
    "                            cnt[c2] -= 1\n",
    "                            ok = True\n",
    "                            break\n",
    "                    if not ok:\n",
    "                        return ans\n",
    "            i -= 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt=Counter(s)\n",
    "        res=sorted(cnt.keys())\n",
    "        ans=\"\"\n",
    "        while res:\n",
    "            temp=res.pop()\n",
    "            if cnt[temp]<=repeatLimit:\n",
    "                ans+=temp*cnt[temp]\n",
    "            else:\n",
    "                ans+=temp*repeatLimit\n",
    "                cnt[temp]-=repeatLimit\n",
    "                if res:\n",
    "                    m=res[-1]\n",
    "                    ans+=m\n",
    "                    cnt[m]-=1\n",
    "                    if cnt[m]==0:\n",
    "                        res.pop()\n",
    "                    res.append(temp)\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq \n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt=collections.Counter(s)\n",
    "        arr=sorted(list(cnt.keys()),reverse=True)\n",
    "        heap=[]\n",
    "        for x in arr:\n",
    "            hq.heappush(heap,-ord(x))\n",
    "        n=len(s)\n",
    "        ans=\"\"\n",
    "        i=0\n",
    "        while len(heap)>=2:\n",
    "            cur=chr(-hq.heappop(heap))\n",
    "            if cnt[cur]>repeatLimit:\n",
    "                nex=chr(-hq.heappop(heap))\n",
    "                ans=ans+cur*repeatLimit+nex\n",
    "                cnt[nex]-=1\n",
    "                cnt[cur]=cnt[cur]-repeatLimit\n",
    "                if cnt[nex]>0:\n",
    "                    hq.heappush(heap,-ord(nex))\n",
    "                hq.heappush(heap,-ord(cur))\n",
    "            else:\n",
    "                ans=ans+cnt[cur]*cur \n",
    "                cnt[cur]=0\n",
    "        if heap:\n",
    "            cur=chr(-hq.heappop(heap))\n",
    "            if cnt[cur]>repeatLimit:\n",
    "                ans=ans+cur*repeatLimit\n",
    "            else:\n",
    "                ans=ans+cnt[cur]*cur \n",
    "\n",
    "\n",
    "        return ans \n",
    "\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Store the number of occurrences of each letter in a dictionary (hash table). \n",
    "    Repeatedly choose the largest possible letter to construct the answer string. \n",
    "    Time complexity: O(n). Space complexity: O(1). \n",
    "    '''\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        letters = 'zyxwvutsrqponmlkjihgfedcba '\n",
    "\n",
    "        freq = {ch: 0 for ch in letters}\n",
    "        for ch in s:\n",
    "            freq[ch] += 1\n",
    "\n",
    "        ans = ''\n",
    "        for i in range(27):\n",
    "            ch = letters[i]\n",
    "            repeatTimes = 0\n",
    "            while freq[ch] > 0:\n",
    "                if repeatTimes < repeatLimit:\n",
    "                    ans += ch\n",
    "                    freq[ch] -= 1\n",
    "                    repeatTimes += 1\n",
    "                else:\n",
    "                    for j in range(i+1, 27):\n",
    "                        if freq[letters[j]] != 0:\n",
    "                            break\n",
    "                        if j == 26:\n",
    "                            return ans\n",
    "                    nextCh = letters[j]\n",
    "                    ans += nextCh\n",
    "                    freq[nextCh] -= 1\n",
    "                    repeatTimes = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        #字母计数\n",
    "        cnt=[0]*26\n",
    "        for i in s:\n",
    "            cnt[ord(i)-97]+=1\n",
    "        ans=\"\"\n",
    "        pre=None\n",
    "        while True:\n",
    "            flag=False\n",
    "            for i in range(25,-1,-1):\n",
    "                ch=chr(i+97)\n",
    "                if cnt[i]==0 or ch==pre:\n",
    "                    continue\n",
    "                flag=True\n",
    "                if cnt[i]<=repeatLimit:\n",
    "                    if pre and pre>ch and cnt[ord(pre)-97]>0:\n",
    "                        ans+=ch\n",
    "                        cnt[i]-=1\n",
    "                    else:\n",
    "                        ans+=ch*cnt[i]\n",
    "                        cnt[i]=0\n",
    "                    pre=ch\n",
    "                    break\n",
    "                else:\n",
    "                    if pre and pre>ch and cnt[ord(pre)-97]>0:\n",
    "                        ans+=ch\n",
    "                        cnt[i]-=1\n",
    "                    else:\n",
    "                        ans+=ch*repeatLimit\n",
    "                        cnt[i]-=repeatLimit\n",
    "                    pre=ch\n",
    "                    break\n",
    "            if not flag:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        counter = Counter(s)\n",
    "        cnt = [[item[0],item[1]] for item in counter.items()]\n",
    "        cnt.sort(key = lambda item:item[0],reverse=True)\n",
    "        sum_repeat = 0\n",
    "        ans = \"\"\n",
    "        while cnt:\n",
    "            if sum_repeat == repeatLimit:\n",
    "                if len(cnt) > 1:\n",
    "                    ans += cnt[1][0]\n",
    "                    cnt[1][1] -= 1\n",
    "                    if cnt[1][1] == 0:\n",
    "                        cnt.pop(1)\n",
    "                    sum_repeat = 0\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                ans += cnt[0][0]\n",
    "                sum_repeat += 1\n",
    "                cnt[0][1] -= 1\n",
    "                if cnt[0][1] == 0:\n",
    "                    cnt.pop(0)\n",
    "                    sum_repeat = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        info = Counter(s)\n",
    "        tmp = sorted(info, key=lambda x:x)\n",
    "        res = \"\"\n",
    "        while tmp:\n",
    "            char = tmp.pop()\n",
    "            if not res or (res and char != res[-1]):\n",
    "                if info[char] <= repeatLimit:\n",
    "                    res += char * info[char]\n",
    "                else:\n",
    "                    res += char * repeatLimit\n",
    "                    info[char] -= repeatLimit\n",
    "                    tmp.append(char)\n",
    "            else:\n",
    "                if tmp:\n",
    "                    char1 = tmp.pop()\n",
    "                    res += char1\n",
    "                    info[char1] -= 1\n",
    "                    if info[char1] > 0:\n",
    "                        tmp.append(char1)\n",
    "                    tmp.append(char)\n",
    "                else:\n",
    "                    return res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt_list = [0] * 26\n",
    "        for char in s:\n",
    "            cnt_list[ord(char) - 97] += 1\n",
    "        \n",
    "        now = 25\n",
    "        while cnt_list[now] == 0:\n",
    "            now -= 1\n",
    "        \n",
    "        next = now - 1\n",
    "        while next >= 0 and cnt_list[next] == 0:\n",
    "            next -= 1\n",
    "\n",
    "        res = ''\n",
    "        while now >= 0:\n",
    "            if cnt_list[now] > repeatLimit:\n",
    "                res += chr(now + 97) * repeatLimit\n",
    "                cnt_list[now] -= repeatLimit\n",
    "                if next < 0:\n",
    "                    break\n",
    "                res += chr(next + 97)\n",
    "                cnt_list[next] -= 1\n",
    "                while next >= 0 and cnt_list[next] == 0:\n",
    "                    next -= 1\n",
    "            else:\n",
    "                res += chr(now + 97) * cnt_list[now]\n",
    "                cnt_list[now] = 0\n",
    "                now = next\n",
    "                next -= 1\n",
    "                while next >= 0 and cnt_list[next] == 0:\n",
    "                    next -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        #字母计数\n",
    "        cnt=[0]*26\n",
    "        for i in s:\n",
    "            cnt[ord(i)-97]+=1\n",
    "        ans=\"\"\n",
    "        pre=None\n",
    "        while True:\n",
    "            flag=False\n",
    "            for i in range(25,-1,-1):\n",
    "                ch=chr(i+97)\n",
    "                if cnt[i]==0 or ch==pre:\n",
    "                    continue\n",
    "                flag=True\n",
    "                if cnt[i]<=repeatLimit:\n",
    "                    if pre and pre>ch and cnt[ord(pre)-97]>0:\n",
    "                        ans+=ch\n",
    "                        cnt[i]-=1\n",
    "                    else:\n",
    "                        ans+=ch*cnt[i]\n",
    "                        cnt[i]=0\n",
    "                    pre=ch\n",
    "                    break\n",
    "                else:\n",
    "                    if pre and pre>ch and cnt[ord(pre)-97]>0:\n",
    "                        ans+=ch\n",
    "                        cnt[i]-=1\n",
    "                    else:\n",
    "                        ans+=ch*repeatLimit\n",
    "                        cnt[i]-=repeatLimit\n",
    "                    pre=ch\n",
    "                    break\n",
    "            if not flag:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        info = Counter(s)\n",
    "        tmp = sorted(info, key=lambda x:x)\n",
    "        res = \"\"\n",
    "        while tmp:\n",
    "            char = tmp.pop()\n",
    "            if not res:\n",
    "                if info[char] <= repeatLimit:\n",
    "                    res += char * info[char]\n",
    "                else:\n",
    "                    res += char * repeatLimit\n",
    "                    info[char] -= repeatLimit\n",
    "                    tmp.append(char)\n",
    "            else:\n",
    "                if char != res[-1]:\n",
    "                    if info[char] <= repeatLimit:\n",
    "                        res += char * info[char]\n",
    "                    else:\n",
    "                        res += char * repeatLimit\n",
    "                        info[char] -= repeatLimit\n",
    "                        tmp.append(char)\n",
    "                else:\n",
    "                    if tmp:\n",
    "                        char1 = tmp.pop()\n",
    "                        res += char1\n",
    "                        info[char1] -= 1\n",
    "                        if info[char1] > 0:\n",
    "                            tmp.append(char1)\n",
    "                        tmp.append(char)\n",
    "                    else:\n",
    "                        return res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = [0] * 26\n",
    "        for x in s:\n",
    "            cnt[ord(x) - ord('a')] += 1\n",
    "        ans = \"\"\n",
    "        i = 25\n",
    "        while i >= 0:\n",
    "            if cnt[i] == 0: \n",
    "                i -= 1\n",
    "                continue\n",
    "            \n",
    "            t = repeatLimit\n",
    "            if cnt[i] > t:\n",
    "                ans += t * chr(i + ord('a'))\n",
    "                cnt[i] -= t\n",
    "                \n",
    "                j = i - 1\n",
    "                ok = False\n",
    "                while j >= 0:\n",
    "                    if cnt[j] > 0:\n",
    "                        ans += 1 * chr(j + ord('a'))\n",
    "                        cnt[j] -= 1\n",
    "                        ok = True\n",
    "                        break\n",
    "                    else:\n",
    "                        j -= 1\n",
    "                        \n",
    "                if not ok: return ans\n",
    "            else:\n",
    "                ans += cnt[i] * chr(i + ord('a'))\n",
    "                cnt[i] = 0\n",
    "                i -= 1\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "\n",
    "        # 题目倒是简单的，就是每次都要选择能选的最大字母，如果都不行的时候就结束\n",
    "        # 麻烦在于怎样把这个逻辑简单一点写出来\n",
    "\n",
    "        # 1、先统计一下每个小写字母的数量\n",
    "        ans = ''\n",
    "        m = [0] * 26\n",
    "        for c in s:\n",
    "            m[ord(c)-ord('a')] += 1\n",
    "        \n",
    "        # 2、确认起始双指针\n",
    "        i = j = -1\n",
    "        for j in range(25, -1, -1):\n",
    "            if m[j]:\n",
    "                break\n",
    "        for i in range(j-1, -1, -1):\n",
    "            if m[i]:\n",
    "                break\n",
    "\n",
    "        # 3、循环操作，把可以配对的全给配对上\n",
    "        while i >= 0 and j >= 0 and i < j and m[i] and m[j]:\n",
    "            ci = chr(ord('a')+i)\n",
    "            cj = chr(ord('a')+j)\n",
    "            if m[j] > repeatLimit:\n",
    "                m[j] -= repeatLimit\n",
    "                m[i] -= 1\n",
    "                ans = ans + cj * repeatLimit\n",
    "                ans = ans + ci\n",
    "            else:\n",
    "                ans = ans + cj * m[j]\n",
    "                m[j] = 0\n",
    "\n",
    "            if m[j] == 0 or m[i] == 0:\n",
    "                for j in range(25, -1, -1):\n",
    "                    if m[j]:\n",
    "                        break\n",
    "                for i in range(j-1, -1, -1):\n",
    "                    if m[i]:\n",
    "                        break\n",
    "\n",
    "        # 4、最后一步，看还有没有有大于零的字符\n",
    "        i = 25\n",
    "        while i:\n",
    "            if m[i] > 0:\n",
    "                break\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            ci = chr(ord('a')+i)\n",
    "            if ans and ans[-1] == ci:\n",
    "                ans = ans + ci * min(repeatLimit-1, m[i])\n",
    "            else:\n",
    "                ans = ans + ci * min(repeatLimit, m[i]) \n",
    "            \n",
    "\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = [0] * 26   # 各个字符出现次数\n",
    "        res = []   # 字典序最大的字符串\n",
    "        r = 0   # 字典序最大的字符对应下标\n",
    "        for ch in s:\n",
    "            cnt[ord(ch)-ord('a')] += 1\n",
    "            r = max(r, ord(ch)-ord('a'))\n",
    "        l = r - 1   # 字典序次大的字符对应下标\n",
    "        while r >= 0:\n",
    "            # 尝试更新 l\n",
    "            while l >= 0 and cnt[l] == 0:\n",
    "                l -= 1\n",
    "            # 尽可能多地添加字典序最大的字符\n",
    "            rep = min(cnt[r], repeatLimit)\n",
    "            for _ in range(rep):\n",
    "                res.append(chr(ord('a')+r))\n",
    "            cnt[r] -= rep\n",
    "            if cnt[r] == 0:\n",
    "                # 字典序最大的字符已用完，次大的变为最大的\n",
    "                r = l \n",
    "                l = r - 1\n",
    "            elif l < 0:\n",
    "                # 此时无法添加新的字符\n",
    "                break\n",
    "            else:\n",
    "                # 添加一个字典序次大的字符，随后继续尝试添加字典序最大的字符\n",
    "                res.append(chr(ord('a')+l))\n",
    "                cnt[l] -= 1\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        kv = [[k, v] for k, v in Counter(s).items()]\n",
    "        kv.sort(reverse=True)\n",
    "        n = len(kv)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while i < n:\n",
    "            if kv[i][1] <= repeatLimit:\n",
    "                ans.append(kv[i][0] * kv[i][1])\n",
    "                i, j = j, j + 1\n",
    "            else:\n",
    "                ans.append(kv[i][0] * repeatLimit)\n",
    "                kv[i][1] -= repeatLimit\n",
    "                if j == n:\n",
    "                    break\n",
    "                ans.append(kv[j][0])\n",
    "                kv[j][1] -= 1\n",
    "                if kv[j][1] == 0:\n",
    "                    j += 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        chrDict = collections.Counter(s)\n",
    "        chrList = sorted(chrDict.keys())\n",
    "        ans = []\n",
    "        flag = False\n",
    "        while chrList:\n",
    "            if chrDict[chrList[-1]] == 0:\n",
    "                chrList.pop()\n",
    "            elif flag:\n",
    "                i = len(chrList) - 2\n",
    "                while i >= 0 and chrDict[chrList[i]] == 0:\n",
    "                    i -= 1\n",
    "                if i == -1: return \"\".join(ans)\n",
    "                ans.append(chrList[i])\n",
    "                chrDict[chrList[i]] -= 1\n",
    "                flag = False\n",
    "            else:\n",
    "                if chrDict[chrList[-1]] <= repeatLimit:\n",
    "                    ans.append(chrList[-1] * chrDict[chrList[-1]])\n",
    "                    chrDict[chrList[-1]] = 0\n",
    "                else:\n",
    "                    ans.append(chrList[-1] * repeatLimit)\n",
    "                    chrDict[chrList[-1]] -= repeatLimit\n",
    "                    flag = True\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = [0] * 26   # 各个字符出现次数\n",
    "        res = []   # 字典序最大的字符串\n",
    "        r = 0   # 字典序最大的字符对应下标\n",
    "        for ch in s:\n",
    "            cnt[ord(ch)-ord('a')] += 1\n",
    "            r = max(r, ord(ch)-ord('a'))\n",
    "        l = r - 1   # 字典序次大的字符对应下标\n",
    "        while r >= 0:\n",
    "            # 尝试更新 l\n",
    "            while l >= 0 and cnt[l] == 0:\n",
    "                l -= 1\n",
    "            # 尽可能多地添加字典序最大的字符\n",
    "            rep = min(cnt[r], repeatLimit)\n",
    "            for _ in range(rep):\n",
    "                res.append(chr(ord('a')+r))\n",
    "            cnt[r] -= rep\n",
    "            if cnt[r] == 0:\n",
    "                # 字典序最大的字符已用完，次大的变为最大的\n",
    "                r = l \n",
    "                l = r - 1\n",
    "            elif l < 0:\n",
    "                # 此时无法添加新的字符\n",
    "                break\n",
    "            else:\n",
    "                # 添加一个字典序次大的字符，随后继续尝试添加字典序最大的字符\n",
    "                res.append(chr(ord('a')+l))\n",
    "                cnt[l] -= 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        pre = \"0\"\n",
    "        num = 0\n",
    "        for _ in range(n):\n",
    "            lst = [x for x in cnt if cnt[x]]\n",
    "            lst.sort(reverse=True)\n",
    "            for w in lst:\n",
    "                if num + int(pre==w) > repeatLimit:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans.append(w)\n",
    "                    num = num+1 if pre==w else 1\n",
    "                    pre = w\n",
    "                    cnt[w] -= 1\n",
    "                    break\n",
    "                \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        str_list = [0] * 26\n",
    "        a_ord = ord('a')\n",
    "        for i in s:\n",
    "            str_list[ord(i) - a_ord] += 1\n",
    "        \n",
    "        temp = 25\n",
    "        nums = [0] * 26\n",
    "        sb = []\n",
    "\n",
    "        while temp >= 0:\n",
    "            for i in range(temp, -1, -1):\n",
    "                if i == 0 and str_list[i] == 0:\n",
    "                    temp = -1\n",
    "                    break\n",
    "                \n",
    "                if str_list[i] == 0:\n",
    "                    temp -= 1\n",
    "                    continue\n",
    "                \n",
    "                sb.append(chr(i + a_ord))\n",
    "                nums[i] += 1\n",
    "                str_list[i] -= 1\n",
    "\n",
    "                if nums[i] == repeatLimit and str_list[i] > 0:\n",
    "                    if i == 0:\n",
    "                        temp = -2\n",
    "                        break\n",
    "                    \n",
    "                    for j in range(i-1, -1, -1):\n",
    "                        if j == 0 and str_list[j] == 0:\n",
    "                            temp = -1\n",
    "                            break\n",
    "                        if str_list[j] != 0:\n",
    "                            sb.append(chr(j + a_ord))\n",
    "                            nums[i] = 0\n",
    "                            str_list[j] -= 1\n",
    "                            break\n",
    "                break\n",
    "        return \"\".join(sb)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        counter = Counter(s)\n",
    "        res, last, last_count = [], '', 0\n",
    "\n",
    "        while True:\n",
    "            if not counter:\n",
    "                break\n",
    "                \n",
    "            op = False\n",
    "            for c in sorted(counter.keys(), reverse=True):\n",
    "                if c == last and last_count >= repeatLimit:\n",
    "                    continue\n",
    "                res.append(c)\n",
    "                counter[c] -= 1\n",
    "                if counter[c]<= 0:\n",
    "                    del counter[c]\n",
    "\n",
    "                if c == last:\n",
    "                    last_count += 1\n",
    "                else:\n",
    "                    last, last_count = c, 1\n",
    "                op = True\n",
    "                break\n",
    "\n",
    "            if not op:\n",
    "                break\n",
    "\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        chrDict = collections.Counter(s)\n",
    "        chrList = sorted(chrDict.keys())\n",
    "        ans = []\n",
    "        flag = False\n",
    "        while chrList:\n",
    "            if chrDict[chrList[-1]] == 0:\n",
    "                chrList.pop()\n",
    "            elif flag:\n",
    "                i = len(chrList) - 2\n",
    "                while i >= 0 and chrDict[chrList[i]] == 0:\n",
    "                    i -= 1\n",
    "                if i == -1: return \"\".join(ans)\n",
    "                ans.append(chrList[i])\n",
    "                chrDict[chrList[i]] -= 1\n",
    "                flag = False\n",
    "            else:\n",
    "                if chrDict[chrList[-1]] <= repeatLimit:\n",
    "                    ans.append(chrList[-1] * chrDict[chrList[-1]])\n",
    "                    chrDict[chrList[-1]] = 0\n",
    "                else:\n",
    "                    ans.append(chrList[-1] * repeatLimit)\n",
    "                    chrDict[chrList[-1]] -= repeatLimit\n",
    "                    flag = True\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        kv = [[k, v] for k, v in Counter(s).items()]\n",
    "        kv.sort(reverse=True)\n",
    "        n = len(kv)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        while i < n:\n",
    "            if kv[i][1] <= repeatLimit:\n",
    "                ans.append(kv[i][0] * kv[i][1])\n",
    "                i, j = j, j + 1\n",
    "            else:\n",
    "                ans.append(kv[i][0] * repeatLimit)\n",
    "                kv[i][1] -= repeatLimit\n",
    "                if j == n:\n",
    "                    break\n",
    "                ans.append(kv[j][0])\n",
    "                kv[j][1] -= 1\n",
    "                if kv[j][1] == 0:\n",
    "                    j += 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        kv = [[k, v] for k, v in Counter(s).items()]\n",
    "        kv.sort(reverse=True)\n",
    "        n = len(kv)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        while i < n:\n",
    "            if kv[i][1] <= repeatLimit:\n",
    "                ans.append(kv[i][0] * kv[i][1])\n",
    "                i, j = j, j + 1\n",
    "            else:\n",
    "                ans.append(kv[i][0] * repeatLimit)\n",
    "                kv[i][1] -= repeatLimit\n",
    "                if j >= n:\n",
    "                    break\n",
    "                ans.append(kv[j][0])\n",
    "                kv[j][1] -= 1\n",
    "                if kv[j][1] == 0:\n",
    "                    j += 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = [0] * 26   # 各个字符出现次数\n",
    "        res = []   # 字典序最大的字符串\n",
    "        r = 0   # 字典序最大的字符对应下标\n",
    "        for ch in s:\n",
    "            cnt[ord(ch)-ord('a')] += 1\n",
    "            r = max(r, ord(ch)-ord('a'))\n",
    "        l = r - 1   # 字典序次大的字符对应下标\n",
    "        while r >= 0:\n",
    "            # 尝试更新 l\n",
    "            while l >= 0 and cnt[l] == 0:\n",
    "                l -= 1\n",
    "            # 尽可能多地添加字典序最大的字符\n",
    "            rep = min(cnt[r], repeatLimit)\n",
    "            for _ in range(rep):\n",
    "                res.append(chr(ord('a')+r))\n",
    "            cnt[r] -= rep\n",
    "            if cnt[r] == 0:\n",
    "                # 字典序最大的字符已用完，次大的变为最大的\n",
    "                r = l \n",
    "                l = r - 1\n",
    "            elif l < 0:\n",
    "                # 此时无法添加新的字符\n",
    "                break\n",
    "            else:\n",
    "                # 添加一个字典序次大的字符，随后继续尝试添加字典序最大的字符\n",
    "                res.append(chr(ord('a')+l))\n",
    "                cnt[l] -= 1\n",
    "        return \"\".join(res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        def add(i):\n",
    "            nonlocal cnt\n",
    "            cnt += 1\n",
    "            char = sort[i]\n",
    "            c[char] -= 1\n",
    "            ans.append(char)\n",
    "            if c[char] == 0:\n",
    "                cnt = 0\n",
    "                del c[char]\n",
    "                if i == -1:\n",
    "                    sort.pop()\n",
    "                else:\n",
    "                    sort.remove(char)\n",
    "\n",
    "        c = Counter(s)\n",
    "        sort = sorted(c)\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        while c:\n",
    "            add(-1)\n",
    "            if cnt == repeatLimit:\n",
    "                if len(sort) == 1:\n",
    "                    break\n",
    "                add(-2)\n",
    "                cnt = 0\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "        map = {}\n",
    "\n",
    "        for c in s:\n",
    "            if c in map:\n",
    "                map[c] += 1\n",
    "            else:\n",
    "                map[c] = 1\n",
    "        \n",
    "        char = [c for c in map]\n",
    "        char.sort(reverse=True)\n",
    "        res = []\n",
    "        ct = 0\n",
    "        \n",
    "        def addChar(repeatLimit, ct, res, map, i, char):\n",
    "            while ct < repeatLimit and map[char[i]] > 0:\n",
    "                res.append(char[i])\n",
    "                prelen = len(res)\n",
    "                ct += 1\n",
    "                map[char[i]] -= 1\n",
    "                for j in range(i):\n",
    "                    addChar(repeatLimit, 0, res, map, j, char)\n",
    "                    if prelen < len(res):\n",
    "                        ct = 0\n",
    "\n",
    "        for i in range(len(char)):\n",
    "            addChar(repeatLimit, 0, res, map, i, char)\n",
    "\n",
    "        return \"\".join(res)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "        cnt = 1\n",
    "        # 双指针\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break \n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2:\n",
    "            return s\n",
    "        map = {}\n",
    "\n",
    "        for c in s:\n",
    "            if c in map:\n",
    "                map[c] += 1\n",
    "            else:\n",
    "                map[c] = 1\n",
    "        \n",
    "        char = [c for c in map]\n",
    "        char.sort(reverse=True)\n",
    "        res = []\n",
    "        \n",
    "        def addChar(repeatLimit, ct, res, map, i, char):\n",
    "            while ct < repeatLimit and map[char[i]] > 0:\n",
    "                res.append(char[i])\n",
    "                prelen = len(res)\n",
    "                ct += 1\n",
    "                map[char[i]] -= 1\n",
    "                for j in range(i):\n",
    "                    addChar(repeatLimit, 0, res, map, j, char)\n",
    "                    if prelen < len(res):\n",
    "                        ct = 0\n",
    "\n",
    "        for i in range(len(char)):\n",
    "            addChar(repeatLimit, 0, res, map, i, char)\n",
    "\n",
    "        return \"\".join(res)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "        \n",
    "        cnt = 1\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        dict1 = {}\n",
    "        for i, c in enumerate(s):\n",
    "            if c in dict1:\n",
    "                dict1[c] += 1\n",
    "            else:\n",
    "                dict1[c] = 1\n",
    "        list_c = list(dict1.keys())\n",
    "        list_c.sort()\n",
    "        list_c = list_c[::-1]\n",
    "        print(dict1, list_c)\n",
    "        # r = repeatLimit\n",
    "\n",
    "        repeat_c = ''\n",
    "        repeat_n = 0\n",
    "        list2 = []\n",
    "        n_c = len(s)\n",
    "\n",
    "        n2 = 0\n",
    "        n3 = 0\n",
    "        while 1:\n",
    "            for c in list_c:\n",
    "                if dict1[c] == 0:\n",
    "                    continue\n",
    "                if repeat_c == c and repeat_n == repeatLimit:\n",
    "                    continue\n",
    "                # print('repeat: {} {} {}'.format(repeat_c, c, repeat_n))\n",
    "                list2.append(c)\n",
    "                dict1[c] -= 1\n",
    "                # print('append {}'.format(c))\n",
    "                \n",
    "                if repeat_c == c:\n",
    "                    repeat_n += 1\n",
    "                else:\n",
    "                    repeat_n = 1\n",
    "                    repeat_c = c\n",
    "                break\n",
    "            if len(list2) == n2:\n",
    "                break\n",
    "            else:\n",
    "                n2 = len(list2)\n",
    "        return ''.join(list2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "            \n",
    "        cnt = 1\n",
    "        # 双指针\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "            \n",
    "        cnt = 1\n",
    "        # 双指针\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "            \n",
    "        cnt = 1\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        # s = sorted(s, reverse=True)\n",
    "        # res, temp = [], []\n",
    "        # count, temp_count = 0, 0\n",
    "        # for item in s:\n",
    "        #     if res and res[-1] != item:\n",
    "        #         count = 0\n",
    "        #     if count < repeatLimit:\n",
    "        #         res.append(item)\n",
    "        #         count += 1\n",
    "        #         while temp and temp_count < repeatLimit:\n",
    "        #             res.append(temp.pop())\n",
    "        #             temp_count += 1\n",
    "        #         temp_count = 0\n",
    "        #     else:\n",
    "        #         temp.append(item)\n",
    "        # return ''.join(res)\n",
    "\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = list()\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "            \n",
    "        cnt = 1\n",
    "        # 双指针\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        # 使用 Counter 统计 s 中每个字符的出现频率\n",
    "        freq = Counter(s)\n",
    "\n",
    "        # 初始化一个空列表 ans，用于存放结果字符串的字符\n",
    "        ans = []\n",
    "\n",
    "        # 按照字典序从大到小的顺序，将 s 中的字符添加到 ans 中\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "\n",
    "        cnt = 1  # 用于记录当前字符连续出现的次数\n",
    "        right = 2  # 初始化右指针\n",
    "\n",
    "        # 使用双指针方法遍历和修正 ans\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "\n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = []\n",
    "        for c in range(25, -1, -1):\n",
    "            ch = chr(ord(\"a\") + c)\n",
    "            ans.extend([ch] * freq[ch])\n",
    "        \n",
    "        cnt = 1\n",
    "        right = 2\n",
    "        for left in range(1, len(ans)):\n",
    "            if ans[left - 1] != ans[left]:\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt > repeatLimit:\n",
    "                    right = max(right, left + 1)\n",
    "                    while right < len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right < len(ans):\n",
    "                        ans[left], ans[right] = ans[right], ans[left]\n",
    "                        cnt = 1\n",
    "                    else:\n",
    "                        ans = ans[: left]\n",
    "                        break\n",
    "        return \"\".join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        #copy zero\n",
    "\n",
    "        freq = Counter(s)\n",
    "        ans = list()\n",
    "        for c in range(25,-1,-1):\n",
    "            ch = chr(ord('a')+c)\n",
    "            ans.extend([ch]*freq[ch])\n",
    "\n",
    "        cnt =1\n",
    "        right = 2\n",
    "        for left in range(1,len(ans)):\n",
    "            if ans[left-1] != ans[left]:\n",
    "                cnt =1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt >repeatLimit:\n",
    "                    right = max(right,left+1)\n",
    "                    while right<len(ans) and ans[left] == ans[right]:\n",
    "                        right += 1\n",
    "                    if right<len(ans):\n",
    "                        ans[left],ans[right] = ans[right],ans[left]\n",
    "                    else:\n",
    "                        ans = ans[:left]\n",
    "                        break\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        sLen = len(s)\n",
    "        ans = ''\n",
    "        s = sorted(s, reverse=True)\n",
    "        cnt = {}\n",
    "        stack = []\n",
    "        for i in range(sLen):\n",
    "            if s[i] not in cnt:\n",
    "                cnt[s[i]] = 1\n",
    "            else:\n",
    "                cnt[s[i]] += 1\n",
    "        for item in cnt:\n",
    "            stack.append([item, cnt[item]])\n",
    "        \n",
    "        prev = None\n",
    "        curr = 0\n",
    "        move = False\n",
    "\n",
    "        while True:\n",
    "            if len(stack) == 0:\n",
    "                break\n",
    "            \n",
    "            move = False\n",
    "            item, count = stack[curr]\n",
    "            \n",
    "            if len(stack) == 1 and stack[0][1] > repeatLimit:\n",
    "                ans += item*repeatLimit\n",
    "                break\n",
    "            \n",
    "            if count > repeatLimit and curr == 0:\n",
    "                ans += item*repeatLimit\n",
    "                stack[curr][1] -= repeatLimit\n",
    "            else:\n",
    "                if curr == 1:\n",
    "                    count = 1\n",
    "                    \n",
    "                if curr == 0 or stack[curr][1] == 1:\n",
    "                    move = True\n",
    "                    stack.pop(curr)\n",
    "                else:\n",
    "                    stack[curr][1] -= count\n",
    "\n",
    "                ans += item*count\n",
    "                \n",
    "\n",
    "            \n",
    "            if curr == 0 and move is False:\n",
    "                curr = 1\n",
    "            else:\n",
    "                curr = 0\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n",
    "        cnt = [0] * 26\n",
    "        r = 0\n",
    "        for c in s:\n",
    "            cnt[ord(c)-ord(\"a\")] +=1 \n",
    "            r = max(r,ord(c)-ord(\"a\")) # 字典序最大的字母位置\n",
    "        l = r-1  # 字典序次大的字母位置\n",
    "        ans = []\n",
    "        while r>=0:\n",
    "            # 字典序次大的且该字母出现次数大于0\n",
    "            while l>=0 and cnt[l]==0:\n",
    "                l-=1 \n",
    "            # 添加字典序最大字母rep次\n",
    "            rep = min(cnt[r],repeatLimit)\n",
    "            ans.extend([chr(ord(\"a\")+r)] * rep)\n",
    "            cnt[r] -= rep \n",
    "            if cnt[r]==0:\n",
    "                r = l \n",
    "                l = r-1 \n",
    "            elif l<0:\n",
    "                break\n",
    "            else:\n",
    "                ans.append(chr(ord(\"a\")+l))\n",
    "                cnt[l]-=1\n",
    "        print(ans)\n",
    "        return \"\".join(ans)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "  \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
